package cn.orange.ch07_binarytree;

import cn.orange.TreeNode;

import java.util.LinkedList;

/**
 * LC222.完全二叉树的节点个数
 给你一棵 完全二叉树 的根节点 root ，求出该树的节点个数
 */
public class LC222 {
    public int countNodes(TreeNode root) {
        /*if (root == null) { //普通二叉树递归（后序）遍历
            return 0;
        }
        return 1 + countNodes(root.left) + countNodes(root.right);*/

        /*int res = 0; //普通二叉树层序遍历
        if (root == null) return res;
        LinkedList<TreeNode> que = new LinkedList<>();
        que.offer(root);
        while (!que.isEmpty()) {
            TreeNode poll = que.poll();
            res++;
            if (poll.left != null) {
                que.offer(poll.left);
            }
            if (poll.right != null) {
                que.offer(poll.right);
            }
        }
        return res;*/
        if (root == null) { //利用完全二叉树特性的解法
            return 0;
        }
        TreeNode left = root.left;
        TreeNode right = root.right;
        int depthL = 0, depthR = 0;
        while (left != null) {
            left = left.left;
            depthL++;
        }
        while (right != null) {
            right = right.right;
            depthR++;
        }
        if (depthL == depthR) {
            return (2 << depthR) - 1;
        }
        return 1 + countNodes(root.left) + countNodes(root.right);
    }
    public static void main(String[] args) {
        LC222 alg = new LC222();
        TreeNode root = new TreeNode(1);
        root.left = new TreeNode(2);
        root.right = new TreeNode(3);
        root.right.left = new TreeNode(6);
        root.left.left = new TreeNode(4);
        root.left.right = new TreeNode(5);
        System.out.println(alg.countNodes(root));
    }
}
